1. Field of the Invention
The present invention generally relates to a navigation device and a guide route search method, and more particularly, to a technique suitable for a navigation device that has a route guide function to automatically search for the most cost-saving route from the current location to a destination with the use of map data.
2. Description of the Related Art
Most navigation devices have a route guide function that enables drivers to easily travel to desired destinations without taking wrong paths. The route guide function automatically searches for the most cost-effective route from the current location to each destination with the use of map data.
The map data used in route searches has a structure that is divided into hierarchical levels based on the variation in the amount of information about a road network. For example, map data divided into three hierarchical levels contain a road mesh called level 0 that covers all roads from narrow streets to expressways, a road mesh called level 1 that mainly covers city roads and roads wider than city roads, and a road mesh called level 2 that covers roads such as expressways and toll roads. Those road meshes are distinguished from one another in the map data. In this case, as the level becomes higher, the map data becomes coarser and contains a smaller amount of information about the road network.
To restrict the amount of arithmetic operation for route searches, calculations are normally performed in the following manner. In the surrounding areas of the current location and a destination, a specific calculation is performed with the use of the map data of the lower level (level 0). In the intermediate region of the route, a rough calculation is performed with the use of the map data of the higher levels (level 1 and higher). The results of both calculations are integrated to output a guide route. Referring now to FIGS. 9A through 9E, a route searching operation according to such a method will be described in detail.
FIGS. 9A through 9E illustrate an operation to search for a guide route from a current location 10 shown in FIG. 9A to a destination 20 shown in FIG. 9E. First, as shown in FIG. 9A, in the surrounding area of the current location 10, a search for a guide route is performed with the use of a road mesh 30 of level 0 that covers all the roads. When the search branch reaches an uplink point 50 to a road mesh 40 of level 1 (the connecting point from the road mesh 30 of level 0 to the road mesh 40 of level 1), a route search is performed by switching to the road mesh 40 of level 1 containing the link corresponding to the uplink point 50, as shown in FIG. 9B. Likewise, the search branch reaches an uplink point 60 to level 2 (the connecting point from the road mesh 40 of level 1 to a road mesh 70 of level 2) after the route search at level 1, a route search is performed by switching to the road mesh 70 of level 2 shown in FIG. 9C.
Meanwhile, in the surrounding area of the destination 20, a route search is performed with the use of a road mesh 80 of level 0 that covers all the roads, as shown in FIG. 9E. When the search branch reaches an uplink point 100 to a road mesh 90 of level 1 while tracing backward from the destination 20, a route search is performed by switching to the road mesh 90 of level 1 containing the link corresponding to the uplink point 100, as shown in FIG. 9D. Likewise, when the search branch reaches an uplink point 110 to level 2 (the connecting point from the road mesh 90 of level 1 to the road mesh 70 of level 2) after the route search at level 1, a route search is performed by switching to the road mesh 70 of level 2 shown in FIG. 9C.
Lastly, the route that connects the uplink point 60 in the road mesh 70 of level 2 determined through the route search from the current location 10 to the uplink point 110 in the road mesh 70 of level 2 determined through the route search from the destination 20 is obtained by performing a route search with the use of the road mesh 70 of level 2. In this manner, the entire route from the current location 10 to the destination 20 is determined, and the guide route searching operation comes to an end.
As the above described route search is performed, there is no need to use the road mesh of level 0 covering all the roads from narrow streets to expressways in all the area, when the route from the current location to a destination is to be determined. Accordingly, the time required for the route search can be shortened. On the other hand, during the searching operation in the intermediate area between the current location and the destination, the road mesh of level 0 is not used. As a result, narrow roads are eliminated from the object routes to be searched in the intermediate area, and, even if there is an actual shortcut among the narrow roads, such a short-cut cannot be found.
To counter this problem, a check is made to determine whether the distance of a guide route calculated by a route search is appropriate with respect to the straight-line distance between the current location and the destination. If the distance is determined not to be appropriate (to be a detour), the map data of the lower level is used to perform a re-searching operation. Such a technique is disclosed in Japanese Patent Application Laid-Open No. 10-153447, for example. Specifically, by the technique disclosed in Japanese Patent Application Laid-Open No. 10-153447, when the ratio between the distance of a guide route calculated through a route search and the straight-line distance between the current location and a destination (the distance of the guide route/the straight-line distance of the guide route) is high, a re-searching operation is performed with the use of the map data of the lower level.
Although the above described problem is not to be solved by this technique, there has been a technique for presenting detours at turning points, as well as guide routes, to users (see Japanese Patent Application Laid-Open No. 2002-243476, for example). By this technique, a turning point at which the traveling direction in a guide route changes, and the road type of the guide route also changes, is identified, and a search is performed with the use of the map data of the lower hierarchical level in the surrounding area of the identified turning point.
By the technique disclosed in Japanese Patent Application Laid-Open No. 10-153447, a re-searching operation is performed with the use of the map data of the lower level, only when the ratio between the distance of a guide route and the straight-line distance of the guide route is higher than a threshold value (or when a route having a large detour is found). Therefore, when a route including partial routes 120 and 130 with partial detours is found as shown in FIG. 10A, a re-searching with the use of the map data of the lower level is not performed if the ratio between the distance of the guide route and the straight-line distance of the guide route is not very high and does not exceed the threshold value. In view of this, to perform a re-searching operation even when a route including a partial detour is found, it is necessary to lower the threshold value to be used to determine whether a re-searching operation should be performed.
In such a case, however, a re-searching operation with the use of the map data of the lower level is performed on the entire guide route, unless the distance of the guide route is almost equal to the straight-line distance of the guide route. For example, in a case where a guide route from which a further shortcut is not to be found through a further re-searching operation is found, as shown in FIG. 10B, a re-searching operation is performed on the entire guide route. If the threshold value is made smaller, a detour route is not to be set as a guide route. However, a longer period of time is required for the re-searching operation, and accordingly, a longer period of time is also required for setting an eventual guide route.
By the technique disclosed in Japanese Patent Application Laid-Open No. 2002-243476, a re-searching operation with the use of the map data of the lower hierarchical level is performed in the surrounding areas of turning points in a guide route found with the use of the map data of the upper hierarchical levels, but a re-searching operation is not performed in the other areas. Therefore, there is no guarantee that no detour routes are included in the areas other than the surrounding areas of the turning points in the guide route. That is, the technique disclosed in Japanese Patent Application Laid-Open No. 2002-243476 does not aim to search for a route including no detours in the first place.